package leetcode.top100;

import leetcode.a_总结分布.Code09_单调栈问题;

import java.util.Stack;

/**
 * 单调栈的应用：
 * 给定一个数组[10,1,8,9,3]，对于任意位置i，从i-1到0找到第一个比 arr[i]大的数
 * 的位置。没有则用-1表示
 * 如：10 -> -1, 1-> 0, 8->0, 9->0, 3->3.
 * 所以输出[-1,0,0,0,3]。
 * <p>
 * 方式1：两次遍历。时间n²
 * <p>
 * 方式2：利用单调栈，时空都是n。
 * 因为找的是比当前位置i大的最近的位置比如是j，那么在j之前小于等于arr[j]的都不会影响
 * 当前位置i的结果。所以忽略删除j之前所有的结果。
 * <p>
 * 利用单调栈，栈存索引，满足后入栈的对应的元素，一定比先前入栈的大。
 * 单调递减栈。
 *
 *
 * 单调栈相关问题{@link Code09_单调栈问题}
 */
public class Code739_AddStack {
    public int[] distanceToHigher1(int[] height) {
        // write code here
        if (height == null || height.length == 0) return null;
        int[] res = new int[height.length];
        res[0] = 0;
        for (int i = 1; i < height.length; i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (height[i] - height[j] < 0) {
                    res[i] = i - j;
                    break;
                }
            }
        }
        return res;
    }


    public int[] distanceToHigher2(int[] height) {
        // write code here
        if (height == null || height.length == 0) return null;
        int[] res = new int[height.length];
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < height.length; i++) {
            //如果当前位置元素大于等于栈内元素，则出栈。因为小于等于height[i]的都不会影响i之后的结果
            //i之后的只要找到i位置即可。
            while (!stack.isEmpty() && height[i] >= height[stack.peek()]) {
                stack.pop();
            }
            //栈顶满足比当前位置元素大。栈顶之前的元素不关心，因为找最近元素。
            res[i] = stack.isEmpty() ? -1 : i - stack.peek();
            //当前位置入栈，给后面元素参考
            stack.push(i);
        }
        return res;
    }


}
